package dfs_bfs.leetcode_200;

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        int islandNum = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    islandNum++;
                    grid[i][j] = '0';
                    // 技巧：将二维数组下标转换为一维数组下标
                    queue.offer(i * cols + j);
                    while (!queue.isEmpty()) {
                        int idx = queue.poll();
                        int row = idx / cols;
                        int col = idx % cols;
                        if (row + 1 < rows && grid[row + 1][col] == '1') {
                            queue.offer((row + 1) * cols + col);
                            grid[row + 1][col] = '0';
                        }
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            queue.offer((row - 1) * cols + col);
                            grid[row - 1][col] = '0';
                        }
                        if (col + 1 < cols && grid[row][col + 1] == '1') {
                            queue.offer(row * cols + col + 1);
                            grid[row][col + 1] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            queue.offer(row * cols + col + 1);
                            grid[row][col - 1] = '0';
                        }
                    }
                }
            }
        }
        return islandNum;
    }
}
